//
// Created by ade on 2022/9/6.
//

#include <iostream>
#include <vector>
#include <string>


using namespace std;

class Solution {
public:
    vector <string> res;
    int len = 0;

    vector <string> combine(vector <vector<int>> &num) {
        len = num.size();
//        dfs(num, 0, "");
        vector <string> combine = {};
        for (auto i:num[0]) {
            combine.push_back(to_string(i));
        }
        bfs(num, combine, 1);
        return res;
    }

    // 深度优先
    void dfs(vector <vector<int>> &num, int index, string s) {
        if (index == len) {
            res.push_back(s);
            return;
        }
        for (auto c : num[index]) {
            s.push_back(c + '0');
            dfs(num, index + 1, s);
            s.pop_back();
        }
    }

    // 广度优先
    void bfs(vector <vector<int>> &num, vector <string> &combine, int index) {
        if (index == len) {
            res = combine;
            return;
        }
        vector <string> tmp = {};
        for (auto c:num[index]) {
            for (auto s: combine) {
                s.push_back(c + '0');
                tmp.push_back(s);
            }
        }

        combine = tmp;
        bfs(num, combine, index + 1);
    }
};

int main() {
    Solution so;
    vector <vector<int>> nums = {
            {1, 2, 4},
            {1, 2, 3},
            {1, 2},
    };
    vector <string> res = so.combine(nums);
    for (auto i : res) {
        cout << i << endl;
    }
    return 0;
}